package sort.test3_31;

public class HeapSort {

    public void sort(int[] nums) {
        if (nums.length == 0) {
            return;
        }
        int length = nums.length;
//  CKG TODO 2023/3/31: 首先找到第一个非叶子节点
        for (int i = length / 2 - 1; i >= 0; i--) {
            adjustHeap(nums, i, length);
        }

        for (int i = length - 1; i > 0; i--) {
            int temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;
            adjustHeap(nums, 0, i);
        }

    }

    public void adjustHeap(int[] nums, int i, int length) {
        int temp = nums[i];
        for (int j = 2 * i + 1; j < length; j = 2 * j + 1) {
            if (j + 1 < length && nums[j] < nums[j + 1]) {
                j++;
            }
            if (nums[j] > temp) {
                nums[i] = nums[j];
                i = j;
            } else {
                break;
            }
        }
        nums[i] = temp;
    }

    public static void main(String[] args) {
      HeapSort heapSort = new HeapSort();
        int[] a={1,5,3,9,4,7};
       heapSort.sort(a);
        for (int b: a
        ) {
            System.out.println(b);

        }

    }

}
